package Prim;

import java.util.Arrays;

public class PrimAlgoritm {
    public static void main(String[] args) {
        //测试看看图是否创建ok
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs = data.length;
        //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
        int [][]weight=new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000},};

        //创建MGraph对象
        MGraph graph = new MGraph(verxs);
        //创建一个MinTree对象
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);
        //输出
        minTree.showGraph(graph);
        //测试普利姆算法
        
        minTree.prim(graph, 0);
    }

}
class MinTree{
    //对graph对象中的权值进行初始化
    public void createGraph(MGraph graph,int verxs,char[] data,int[][] weight){
        int i,j;
        for (i = 0;  i<verxs ; i++) {
             //将值一个个放入到graph 的char数组data中
            graph.data[i]=data[i];
            for (j=0;j<verxs;j++){
                graph.weight[i][j]=weight[i][j];
            }
        }
    }
    //把权值输出
    public void showGraph(MGraph graph){
        for(int[] link: graph.weight) {
            System.out.println(Arrays.toString(link));
        }
    }

    /**
     * 普里姆算法
     * @param graph 需要求解的图
     * @param v 从哪个节点开始
     */
    public void prim(MGraph graph,int v){
        //定义一个数组，用于记录每个节点的访问情况
        int[] visited = new int[graph.verxs];
        visited[v]=1;
        //h1 和 h2 记录两个顶点的下标
        int h1 = -1;
        int h2 = -1;
        //minWeight记录当前最下的权值,初始为10000 意为不连通，权值无穷大
        int minWeight=10000;
        //遍历边，数量为graph.verxs-1,故从1开始
        for(int k=1;k<graph.verxs;k++){
            //用i循环访问过的边
            for (int i = 0; i < graph.verxs; i++) {
                //用j访问没有访问过的边
                for (int j=0;j<graph.verxs;j++){
                    //i访问到的边必须是被访问过的，j访问的节点必须是没有被访问的
                    //且i所代表的节点和j所代表的节点 两个节点的边的权值比如比当前minWeight所记录的要小
                    if(visited[i]==1&&visited[j]==0&&graph.weight[i][j] <minWeight){
                        minWeight=graph.weight[i][j];
                        h1=i; //记录下当前的访问的节点
                        h2=j; //记录下当前的访问的节点
                    }
                }
            }
            //两层for循环结束，表明已经找到了两个节点权值最小的边
            //找到一条边是最小
            System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);
            //h2所指向的节点应置为1
            visited[h2]=1;
            //将minWeight置为10000,便于下次的权值比较
            minWeight=10000;
        }
    }

}
class MGraph{
     int verxs;//表示图的节点个数
     char[] data;//存放节点数据
     int[][] weight;//边的权重

    public MGraph(int verxs) {
        this.verxs = verxs;
        data = new char[verxs];
        weight=new int[verxs][verxs];
    }
}
